package leetcode.todo

import kotlinetc.println
import leetcode.merge

/**
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Accepted
177,895
Submissions
569,390
 */
fun main(args: Array<String>) {

    val intervals = arrayOf(
            intArrayOf(1, 3),
            intArrayOf(6, 9)
    )

    val interval1 = arrayOf(
            intArrayOf(1, 2),
            intArrayOf(3, 5),
            intArrayOf(6, 7),
            intArrayOf(8, 10),
            intArrayOf(12, 16))

    //1,5  0,3

    //[[2,4],[5,7],[8,10],[11,13]]
    //[3,6]
    insert(arrayOf(intArrayOf(2,4),
            intArrayOf(5,7),
            intArrayOf(8,10),
            intArrayOf(11,13)),
            intArrayOf(3,6))
            .forEach { it.asList().println() }
}


/**
 * 和 [merge] 题目基本差不多，插入之后得到一个新的区间，然后从该区间开始合并后续区间
 */
fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {

    if (intervals.isEmpty()) return arrayOf(newInterval)

    var i = 0
    val result = arrayListOf<IntArray>()

    if (newInterval[1]<intervals[0][0]){
        result.add(newInterval)
        result.addAll(intervals.toList())
        return result.toTypedArray()
    }

    var merged = false

    while (i < intervals.size) {
        val intArr = intervals[i]
        if ((newInterval[0] <= intArr[1] &&newInterval[0]>=intArr[0])||
                (intArr[0] <= newInterval[1]&&intArr[0]>=newInterval[0])) {
            merged = true
            //开始往后面合并到不能合并为止，然后返回
            val start = Math.min(newInterval[0], intArr[0])
            var end = Math.max(newInterval[1], intArr[1])
            var k = i + 1
            while (k < intervals.size) {
                val arr = intervals[k]
                if (arr[0] <= end) {
                    end = Math.max(end, arr[1])
                } else {

                    break
                }
                k++
            }
            result.add(intArrayOf(start, end))
            i = k
            if (i < intervals.size)
                result.add(intervals[i])


        } else {
            result.add(intArr)
        }
        i++

    }

    //如果找到最后一个也无法合并，就把newinterval加到最后
    if (merged.not())
        result.add(newInterval)

    //可能newInterval 需要插入到中间某个位置，而我们加入到了最后，所以还需要一次排序
    result.sortBy { it[0] }

    return result.toTypedArray()
}